package com.zklh.leetcode.top100.problem20;

import java.util.*;

/**
 * 有效的括号， 算法实现
 */
public class Solution20 {
    public boolean isValid(String s) {
        // 左右括号的映射关系
        Map<Character, Character> rightToLeftBracket = new HashMap<>();
        // 使用栈做处理容器， 当遇到左括号， 入栈， 当遇到可闭合括号， 出栈，
        Deque<Character> bracketDeque = new LinkedList<>();

        // 初始化map
        rightToLeftBracket.put(')','(');
        rightToLeftBracket.put('}','{');
        rightToLeftBracket.put(']','[');

        /* 对字符串进行处理 */
        for (char c : s.toCharArray()) {
            // 左括号入栈
            if (!rightToLeftBracket.containsKey(c)) {
                bracketDeque.push(c);
            } else { // 右括号出栈， 无法闭合的右括号则是无效字符
                if (rightToLeftBracket.get(c).equals(bracketDeque.peek())) {
                    bracketDeque.poll();
                } else {
                    return false;
                }
            }
        }
        return bracketDeque.isEmpty();
    }

    public static void main(String[] args) {
        String s = "(){}[]";
        Solution20 solution = new Solution20();
        System.out.println(solution.isValid(s));
        System.out.println('{'+0);
        System.out.println('}'+0);
    }
}
